#pragma once

#include <iostream>


template<typename T>
class DLinkedList
{
public:
	struct Node
	{
		Node():data(),prev(nullptr),next(nullptr)
		{};

		Node(T inData):data(inData),prev(nullptr),next(nullptr)
		{};

		Node* GetPrev() const {return prev;};
		Node* GetNext() const {return next;};
		
		T data;
		Node* prev; // 前驱节点
		Node* next; // 后继节点
	};

	DLinkedList();
	~DLinkedList();

	int Size() const;

	void ShowData();

	/**
	 * 末端插入
	 * @param element 
	 */
	void Insert(T element);

	/**
	 * 指定位置插入
	 * @param index 
	 * @param element 
	 */
	void Insert(int index, T element);
	void Remove(int index);
	T& operator[](int index);
	Node* GetNode(int index) const;
private:
	int size;
	Node* head;
};

template <typename T>
DLinkedList<T>::DLinkedList():
	size(0),
	head(nullptr)
{
}

template <typename T>
DLinkedList<T>::~DLinkedList()
{
	Node* deletedNode = nullptr;
	Node* temp = head;
	std::cout << "delete: ";
	while (temp)
	{
		deletedNode = temp;
		temp = temp->next;

		std::cout << deletedNode->data << " ";
		delete deletedNode;
	}
}

template <typename T>
int DLinkedList<T>::Size() const
{
	return size;
}

template <typename T>
void DLinkedList<T>::ShowData()
{
	std::cout << "Show DLinkedList: \n";
	std::cout << "Size: " << size << "\n";

	Node* temp = head;
	if (!temp)
		return;
	
	std::cout << temp->data;
	temp = temp->next;
	while (temp)
	{
		std::cout << " <-> " << temp->data;
		temp = temp->next;
	}

	std::cout << std::endl;
}

template <typename T>
void DLinkedList<T>::Insert(T element)
{
	if (head)
	{
		// 如果 head 不为空
		
		Node* temp = head;
		// 如果 next 为空，说明 temp 是末端节点
		while(temp->next)
			temp = temp->next;

		temp->next = new Node(element);
		temp->next->prev = temp;
	}
	else
	{
		// 如果 head 为空
		head = new Node(element);
	}

	++size;
}

template <typename T>
void DLinkedList<T>::Insert(int index, T element)
{
	if (index < 0 || index > size)
		return;

	if (head)
	{
		// 如果 head 不为空
		Node* temp = head;
		if (index == 0)
		{
			head = new Node(element);
			head->next = temp;
			temp->prev = head;
		}
		else if (index == 1)
		{
			temp = head->next;
			head->next = new Node(element);
			head->next->prev = head;

			head->next->next = temp;
			temp->prev = head->next;
		}
		else
		{
			// 找到对应索引的前驱节点
			for(int i = 0; i < index - 1; ++i)
				temp = temp->next;

			Node* newNode = new Node(element);
			newNode->prev = temp;
			newNode->next = temp->next;

			temp->next = newNode;
			newNode->next->prev = newNode;
		}

		++size;
	}
	else
	{
		// 如果 head 为空
		Insert(element);
	}
}

template <typename T>
void DLinkedList<T>::Remove(int index)
{
	if (index < 0 || index >= size)
		return;

	Node* deletedNode = head;
	if (index == 0)
	{
		head = head->next;
	}
	else if (index == 1)
	{
		deletedNode = head->next;
		head->next = head->next->next;
		
	}
	else
	{
		Node* temp = head;
		// 找到对应索引的前驱节点
		for (int i = 0; i < index - 1; ++i)
			temp = temp->next;

		deletedNode = temp->next;
		temp->next = temp->next->next;
	}
	
	delete deletedNode;
	--size;
}

template <typename T>
T& DLinkedList<T>::operator[](int index)
{
	Node* temp = head;
	for (int i = 0; i <= index; ++i)
		temp = temp->next;

	return temp->data;
}

template <typename T>
typename DLinkedList<T>::Node* DLinkedList<T>::GetNode(int index) const
{
	if (index < 0 || index >= size)
		return nullptr;
	
	Node* temp = head;
	for (int i = 0; i < index; ++i)
		temp = temp->next;

	return temp->next;
}
